package array;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * leet-code(34) 在排序数组中查找元素的第一个和最后一个位置
 *
 * @author Ringo
 * @date 2021/8/22 22:19
 */
public class SearchRange {

    public static void main(String[] args) {
        int[] nums = {5, 7, 7, 8, 8, 8, 8, 10};
        int first = search(nums, 8, true);
        int last = search(nums, 8, false);
        System.out.println(Arrays.asList(first, last));
    }

    /**
     * 二分查找
     *
     * @param leftOrRight <code>true</code> 查找第一个 <br/>
     *                    <code>false</code> 查找最后一个
     */
    public static int search(int[] nums, int target, boolean leftOrRight) {
        int lo = 0, hi = nums.length - 1;
        int ans = -1;
        while (lo <= hi) {
            int mid = (lo + hi) >> 1;
            if (target < nums[mid])
                hi = mid - 1;
            else if (target > nums[mid])
                lo = mid + 1;
            else {
                ans = mid;
                if (leftOrRight)
                    hi = mid - 1;
                else
                    lo = mid + 1;
            }
        }
        return ans;
    }

    /**
     * 暴力解法
     */
    public static int[] searchRange(int[] nums, int target) {
        List<Integer> list = new ArrayList<>(nums.length);
        for (int num : nums) {
            list.add(num);
        }
        int first = list.indexOf(target);
        int last = list.lastIndexOf(target);
        return new int[]{first, last};
    }
}
